package linkedlist;

public class MyLinkedList {

    /**
     * 数据
     */
    private MyNode head;
    /**
     * 节点的个数
     */
    int size = 0;

    /**
     * 插入链表头部
     */
    public void addHead(String data){
        MyNode newNode = new MyNode(data);
        // head = newNode;  如果head 为 null，可以这么写
        // 但如果 head有值了呢?再插入一个值到头部，原有的值就会被覆盖
        newNode.next = head;
        head = newNode;
        size++;
    }

    /**
     * 添加节点到链表尾部
     */
    public void add(String data){
        MyNode newNode = new MyNode(data);
        MyNode cur = head;
        //遍历到末尾元素 末尾元素 next 指向 null
        while (cur.next != null){
            cur = cur.next;
        }
        //直接将末尾的 next 指向新元素
        cur.next = newNode;
        size++;
    }

    /**
     * 指定下标添加链表节点
     */
    public void add(int index,String data){
        //下标越界
        if (index > size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //判断是否添加的是头结点
        if(index == 0){
            addHead(data);
        } else {
            // 如果不是头节点，则需要进行遍历，获得下标前一个节点
            //比如源链表 1、2、3、4 ，在下标为 2 插入节点 5
            //目标链表为 1、2、5、3、4
            //1、因为单链表只有 next 指针，所以要找到指定下标节点的前一个节点
            //2、如果 index 不减 1，当需要在尾部添加节点时，会出现空指针
            MyNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            MyNode newNode = new MyNode(data);
            //将下标节点与新节点关联起来
            newNode.next = cur.next;
            //next 指向新节点
            cur.next = newNode;
            size++;
        }
    }


    /**
     * 根据下标删除节点
     */
    public void remove(int index){
        //下标越界
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        MyNode cur = head;
        //如果删除头节点
        if(index == 0){
            removeHead();
            return;
        }
        //找到指定下标节点的前一个节点
        for (int i = 0; i < index -1; i++) {
            cur = cur.next;
        }
        //跳过要删除元素的指向
        cur.next = cur.next.next;
        size--;
    }

    /**
     * 删除链表头节点
     */
    private void removeHead(){
        if(head == null){
            return;
        }
        //获得头节点的下个节点
        MyNode headNext = head.next;
        //将下个节点赋值给头节点
        head = headNext;
        size--;
    }

    /**
     * 删除链表尾节点
     */
    public void removeTail(){
        remove(size -1);
    }
    /**
     * 修改指定下标节点值
     */
    public void set(int index,String data){
        //下标越界
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //获得指定下标节点
        MyNode node = getNode(index);
        node.item = data;
    }

    /**
     * 获得指定下标节点的值
     */
    public String get(int index){
        //下标越界
        if (index >= size || index < 0){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        //获得指定下标节点
        MyNode node = getNode(index);
        return node.item;
    }

    public void print(){
        MyNode cur = head;
        while (cur != null){
            System.out.println(cur.item + " ");
            cur = cur.next;
        }
    }

    /**
     *  获得指定下标节点
     */
    private MyNode getNode(int index){
//        MyNode cur = head;
//        for (int i = 0; i < index; i++) {
//            cur = cur.next;
//        }
        MyNode prev = head;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;
        return prev;
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        System.out.println("添加头节点");
        myLinkedList.addHead("2");
        myLinkedList.addHead("1");
        myLinkedList.print();
        System.out.println("在尾部添加节点");
        myLinkedList.add("3");
        myLinkedList.add("4");
        myLinkedList.print();
        System.out.println("指定下标添加节点");
        MyNode node = myLinkedList.getNode(4);
        System.out.println(node);
        //myLinkedList.add(4,"666");
       // myLinkedList.add(5,"777");
       // myLinkedList.add(2,"888");
        myLinkedList.print();
//        System.out.println("指定下标删除节点");
//        myLinkedList.remove(0);
//        myLinkedList.remove(5);
//        myLinkedList.removeHead();
//        myLinkedList.removeTail();
//        myLinkedList.print();

//        System.out.println("指定下标修改节点");
//        myLinkedList.set(0,"cxyxj");
//        myLinkedList.print();
//        System.out.println("指定下标获得节点");
//       System.out.println(myLinkedList.get(0));

    }
}

class MyNode{

    /**
     * 值
     */
    String item;
    /**
     * 下一个节点的指针
     */
    MyNode next;

    MyNode(String item){
        this.item = item;
        this.next = null;
    }
}